public class BinarySearchBalance {

    /**
     * 二分查找平衡版
     *
     * @param A      : 有序数组a
     * @param target : 目标查找值
     * @return 返回索引值
     */
    public static int binarySearchBalance(int[] A, int target) {
        // 定义左右边界,左边i指针对应的值可能target , 右指针j作为边界, 必须不参与运算比较
        int i = 0, j = A.length;
        // 定义循环条件 , 目的为缩小比较范围,将最后比较功能放到循环以外
        // 由i < j => 0 < j - i 改为 1 < j - i; 表示[i , j]区间内待比较的个数是否有1个以上
        while (1 < j - i) {
            // 定义中间索引
            int m = (i + j) >>> 1;
            if (target < A[m]) {
                // j作为右边界,不参与比较.故当判断出来target值在m指针左侧时,m指针对应值已经判断过了,不可能和target相等,让j=m,及让j作为一个不可能相等的边界使用
                j = m;
            } else {
                // 及 A[m] <= target的情况,及 i指针对应的值是有可能为target结果的
                i = m;
            }
        }
        // 将缩减范围后剩余的一个索引i所对应的值与target进行比较
        if (A[i] == target){
            return i;
        } else {
            return -1;
        }
    }
}
